package Sort.sort2020;

/**
 * 快速排序
 *
 * @author leiwenkang
 * @date 2020/3/29
 */
public class QuickSort {
    public static void main(String[] args) {
        int[] array = {3, 8, 4, 6, 7, 2, 5, 9, 1};
        quickSort(array);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]);
            System.out.print(" ");
        }
    }

    public static void quickSort(int[] array) {
        if (array == null || array.length == 0) {
            return;
        }
        quickSort(array, 0, array.length - 1);
    }

    public static void quickSort(int[] array, int low, int high) {
        if (low >= high) {
            return;
        }
        int partion = partion(array, low, high);
        quickSort(array, low, partion - 1);
        quickSort(array, partion + 1, high);
    }

    private static int partion(int[] array, int low, int high) {
         int val = array[low];
         while (low < high) {
             while (low < high && array[high] >= val) {
                 high--;
             }
             array[low] = array[high];
             while (low < high && array[low] <= val) {
                 low++;
             }
             array[high] = array[low];
         }
         array[high] = val;
         return high;
    }
}
